package leetCode.offer14_ii;

import java.math.BigDecimal;

/**
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？
 * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 * 示例 1：
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 *
 * 示例2:
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 ×3 ×4 = 36
 *
 * 提示：
 * 2 <= n <= 1000
 */
public class Solution1 implements Solution {

    /**
     * 解法：对这个题目，我们可以先采用举例法看看有什么规律
     * 定义f(n) 就是n的最大乘积
     * f(1) = 0
     * f(2) = 1
     * f(3) = 1*2 = 2
     *
     * g(1) = 1
     * g(2) = 2
     * g(3) = 3
     * f(4) = 2*2 = 4 = g(2)*g(2)  g(4) = 4
     * f(5) = 2*3 = 6 = g(2)*g(3)  g(5) = 6
     * f(6) = 3*3 = 9 = g(3)*g(3)  g(6) = 9
     * f(7) = 2*2*3 = 12 = g(3)*g(4) g(7) = 12
     * @param n
     * @return
     */
    @Override
    public int cuttingRope(int n) {
        if(n<2) return 0;
        if(n==2) return 1;
        if(n==3) return 2;

        BigDecimal[] tem = new BigDecimal[n+1];
        tem[1] = new BigDecimal(1);
        tem[2] = new BigDecimal(2);
        tem[3] = new BigDecimal(3);
        BigDecimal max ;
        for(int i=4;i<n+1;i++) {
            max = new BigDecimal(0);
            for(int j=1;j<=i/2;j++) {
                BigDecimal mul = (tem[j].multiply(tem[i-j]));
                if(max .compareTo( mul)<0) {
                    max = mul;
                }
                tem[i] = max;
            }
        }
        return tem[n].divideAndRemainder(BigDecimal.valueOf(1000000007))[1].intValue();
    }

    public static void main(String[] args) {
        Solution solution = new Solution1();
        //556038130
        System.out.println(solution.cuttingRope(800));
    }

}
